type 'a tree =
    Br of 'a * 'a tree * 'a tree
  | Lf

let rec size tr =
  match tr with
    Br (_, l, r) -> 1 + size l + size r
  | Lf -> 0

let rec total tr =
  match tr with
    Br (x, l, r) -> x + total l + total r
  | Lf -> 0

let max x y =
  if x > y then x else y

let rec maxdepth tr =
  match tr with
    Br (_, l, r) -> 1 + max (maxdepth l) (maxdepth r)
  | Lf -> 0

let rec list_of_tree tr =
  match tr with
    Br (x, l, r) -> list_of_tree l @ [x] @ list_of_tree r
  | Lf -> []

let rec tree_map f tr =
  match tr with
    Br (x, l, r) -> Br (f x, tree_map f l, tree_map f r)
  | Lf -> Lf

let rec lookup tr k =
  match tr with
    Lf -> raise Not_found
  | Br ((k', v), l, r) ->
      if k = k' then v
      else if k < k' then lookup l k
      else lookup r k

let rec lookup tr k =
  match tr with
    Lf -> None
  | Br ((k', v), l, r) ->
      if k = k' then Some v
      else if k < k' then lookup l k
      else lookup r k

let rec insert tr k v =
  match tr with
    Lf -> Br ((k, v), Lf, Lf)
  | Br ((k', v'), l, r) ->
      if k = k' then Br ((k, v), l, r)
      else if k < k' then Br ((k', v'), insert l k v, r)
      else Br ((k', v'), l, insert r k v)

(* q1 *)
let rec member_tree i t = 
  match t with
    Lf -> false
  | Br(v, l, r) -> v = i || (member_tree i l) || (member_tree i r)

(* q2 *)
let rec flip_tree t = 
  match t with
    Lf -> Lf
  | Br(v, l, r) -> Br(v, flip_tree r, flip_tree l)

(* q3 *)
let rec same_tree t1 t2 = 
  match t1, t2 with
    Lf, Lf -> true
  | Br(_, l, r), Br(_, l', r') -> same_tree l l' && same_tree r r'
  | _ -> false

(* q4 *)
let tree_of_list l = 
  List.fold_left
    (fun acc (k, v) -> insert acc k v)
    Lf l

(* q5 *)
let comb_tree t1 t2 = 
  let t1 = list_of_tree t1 in
  List.fold_left
    (fun acc (k, v) -> insert acc k v)
    t2 t1

(* q6 *)
type 'a tree =
    Br of 'a * ('a tree) list
  | Lf

let rec size tr = 
  match tr with
    Lf -> 0
  | Br(_, sub_tr) ->
      1 + List.fold_left (fun acc i -> acc + size i) 0 sub_tr

let rec total tr = 
  match tr with
    Lf -> 0
  | Br(x, sub_tr) ->
      x + List.fold_left (fun acc i -> acc + total i) 0 sub_tr

let rec map f tr = 
  match tr with
    Lf -> Lf
  | Br(x, sub_tr) ->
      Br(f x, List.map (map f) sub_tr)